#include <bits/stdc++.h>
using namespace std;

class Solution1 {
public:
	bool repeatedSubstringPattern(string s) {
		string newStr = s + s;
		newStr.erase(0,1);
		newStr.erase(newStr.size()-1,1);
		if(newStr.find(s) != string::npos){
			return true;
		}
		return false;
	}
};

class Solution2 {
public:
	void getNext(int next[],string s){
		int j = 0;
		next[0] = 0;
		for(int i = 1;i < s.size();i++){
			while(s[i] != s[j] && j > 0){
				j = next[j-1];
			}
			if(s[i] == s[j]){
				j++;
			}
			next[i] = j;
		}
	}
	bool repeatedSubstringPattern(string s) {
		if(s.size() == 0){
			return false;
		}
		int* next = new int[s.size()];
		getNext(next,s);
		int len = s.size();
		int maxLen = next[s.size()-1];
		if(maxLen != 0 && (len % (len - maxLen)) == 0){
			return true;
		}
		return false;
	}
};

class Test{
public:
	void getNext(int* next,string& s){
		int j = 0;
		next[0] = 0;
		for(int i = 1;i < s.size();i++){
			while(s[i] != s[j] && j > 0){
				j = next[j - 1];
			}
			if(s[i] == s[j]){
				j++;
			}
			next[i] = j;
		}
	}
	bool repeatedSubstringPattern(string s){
		if(s.size() == 0){
			return false;
		}
		int* next = new int[s.size()];
		getNext(next,s);
		int maxLen = next[s.size()-1];
		int len = s.size();
		if(maxLen!=0&&(len % (len - maxLen)) == 0){
			return true;
		}
		return false;
		
		
	}
	
};

int main(){
	string s = "abab";
	Test so;
	bool res = so.repeatedSubstringPattern(s);
	cout << res << endl;
	return 0;
}
